package cn.lena.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

//贪心算法
public class Greedy {

	//两地调度
	/*
		公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[0][i]，飞往 B 市的费用为 costs[1][i]。
		返回将每个人都飞到某座城市的最低费用，要求每个城市都有 N 人抵达。
	*/
	public static int twoCitySchedCost(int[][] costs) {
		int allMoneys=0;    //存取所有花费。
		//计算所有人员发往A城市所需要的钱
		for(int i=0;i<costs[0].length;i++){
			allMoneys += costs[0][i];
		}
		//System.out.println(allMoneys);
		//计算costs[0][i]-costs[1][i]的值
		for(int i=0;i<costs[0].length;i++){
			costs[0][i]=costs[0][i]-costs[1][i];
		//	System.out.println(costs[0][i]);
		}
		//按照从小到大排序。大的即表示到城市A的费用大于到城市B
		Arrays.sort(costs[0]);
		//System.out.println(costs[0][0]+"---"+costs[0][1]+"---"+costs[0][2]+"---"+costs[0][3]);
		//选择后N人去B城市
		for (int i=costs[0].length-1;i>=costs[0].length/2;i--){
			allMoneys -= costs[0][i];
		//	System.out.println("减去"+costs[0][i]+"元，有---"+allMoneys);
		}
		return allMoneys;
	}


	//广播电台的选取
	public static ArrayList<String> broadcasting(HashSet<String> allAreas,HashMap<String, HashSet<String>> broadcasts){
		//创建ArrayList, 存放已经选择的电台集合
		ArrayList<String> selects = new ArrayList<String>();

		//定义一个临时的集合， 在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
		HashSet<String> tempSet = new HashSet<String>();

		//定义给maxKey ， 保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key
		//如果maxKey 不为null , 则会加入到 selects
		String maxKey = null;
		while(allAreas.size() != 0) { // 如果allAreas 不为0, 则表示还没有覆盖到所有的地区
			//每进行一次while,需要
			maxKey = null;

			//遍历 broadcasts, 取出对应key
			for(String key : broadcasts.keySet()) {
				//每进行一次for，清空交集tempSet
				tempSet.clear();
				//当前这个key能够覆盖的地区
				HashSet<String> areas = broadcasts.get(key);
				tempSet.addAll(areas);
				//求出tempSet 和   allAreas 集合的交集(表示当前存在未加入的电台), 交集会赋给 tempSet
				tempSet.retainAll(allAreas);
				//如果当前这个集合包含的未覆盖地区的数量，比maxKey指向的集合地区还多(寻找最优解)
				//就需要重置maxKey
				// tempSet.size() >broadcasts.get(maxKey).size()) 体现出贪心算法的特点,每次都选择最优的
				if(tempSet.size() > 0 &&
						(maxKey == null || tempSet.size() >broadcasts.get(maxKey).size())){
					maxKey = key;		//将maxkey指向这里
				}
			}
			//maxKey != null, 就应该将maxKey 加入selects
			if(maxKey != null) {
				selects.add(maxKey);
				//将maxKey指向的广播电台覆盖的地区，从 allAreas 去掉
				allAreas.removeAll(broadcasts.get(maxKey));
			}

		}

		return selects;

	}

}
